package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-26 16:05
 */


import java.util.Deque;
import java.util.LinkedList;

/**
 * 移掉 K 位数字
 * 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。
 * 请你以字符串形式返回这个最小的数字。
 */
public class lc402 {
    public String removeKdigits(String num, int k) {

        //双端队列
        Deque<Character> deque = new LinkedList<>();
        int len = num.length();

        //将数字递增的加入队列
        for (int i = 0; i < len; i++) {
            char ch = num.charAt(i);
            //当且仅当K>0 并且队尾元素大于要入队的元素的时候就把队尾元素移除掉
            while (!deque.isEmpty() && k > 0 && ch < deque.peekLast()) {
                deque.pollLast();
                k--;
            }
            deque.addLast(ch);
        }
        //此时如果K还大于0 队列里面的元素已经为单调不降了。则最后依次移除队列尾部剩余的k数次即可，
        //拿123456728 k=7 举例说明
        //入队完后 队列里面为1228 此时k=2 所以还需要依次移除尾部2和8  剩余12即为最小
        for (int i = 0; i < k; i++) {
            deque.pollLast();
        }
        //用来标识第一个零
        boolean flag = true;
        StringBuilder ans = new StringBuilder();
        //从队列头部取出所有元素
        while (!deque.isEmpty()) {
            Character character = deque.pollFirst();
            if (flag&&character=='0'){
                continue;
            }
            flag =false;//首位不为零后改变flag的状态，后面的零不再清除
            ans.append(character);
        }
        //返回结果
        return ans.length() == 0 ? "0" : ans.toString();
    }
}
